
@article{chen-spaa,
  author    = {Jen-Yeu Chen and
               Gopal Pandurangan},
  title     = {Almost-Optimal Gossip-Based Aggregate Computation},
  journal   = {SIAM J. Comput.},
  volume    = {41},
  number    = {3},
  year      = {2012},
  pages     = {455-483}
  }


@inproceedings{soda12,
  author    = {John Augustine and
               Gopal Pandurangan and
               Peter Robinson and
               Eli Upfal},
  title     = {Towards robust and efficient computation in dynamic peer-to-peer
               networks},
  booktitle = {SODA},
  year      = {2012},
  pages     = {551-569}
}

@inproceedings{disc12,
  author    = {Atish Das Sarma and
               Anisur Rahaman Molla and
               Gopal Pandurangan},
  title     = {Fast Distributed Computation in Dynamic Networks via Random
               Walks},
  booktitle = {DISC},
  year      = {2012},
  pages     = {136-150}
}

@inproceedings{podc13,
  author    = {John Augustine and
               Gopal Pandurangan and
               Peter Robinson},
  title     = {Fast byzantine agreement in dynamic networks},
  booktitle = {PODC},
  year      = {2013},
  pages     = {74-83}
}

@inproceedings{spaa13,
  author    = {John Augustine and
               Anisur Rahaman Molla and
               Ehab Morsy and
               Gopal Pandurangan and
               Peter Robinson and
               Eli Upfal},
  title     = {Storage and search in dynamic peer-to-peer networks},
  booktitle = {SPAA},
  year      = {2013},
  pages     = {53-62}
}

@inproceedings{chen,
  author    = {Chen Avin and
               Michal Kouck{\'y} and
               Zvi Lotker},
  title     = {How to Explore a Fast-Changing World (Cover Time of a Simple
               Random Walk on Evolving Graphs)},
  booktitle = {ICALP (1)},
  year      = {2008},
  pages     = {121-132}
}

@inproceedings{podc12,
  author    = {Andrea E. F. Clementi and
               Riccardo Silvestri and
               Luca Trevisan},
  title     = {Information spreading in dynamic graphs},
  booktitle = {PODC},
  year      = {2012},
  pages     = {37-46}
}

@inproceedings{podc08,
  author    = {Andrea E. F. Clementi and
               Claudio Macci and
               Angelo Monti and
               Francesco Pasquale and
               Riccardo Silvestri},
  title     = {Flooding time in edge-Markovian dynamic graphs},
  booktitle = {PODC},
  year      = {2008},
  pages     = {213-222}
}

@inproceedings{icalp14,
  author = {George Giakkoupis and Thomas Sauerwald and Alexandre Stauffer},
title = {Randomized Rumor Spreading in Dynamic Graphs},
booktitle = {ICALP(2)},
 year = {2014},
 pages ={495-507}
}

@article{ozalp1,
  title = {T-MAN: Gossip-based fast overlay topology construction},
  author = {Mark Jelasity and Alberto Montresor and Ozalp Babaoglu},
  journal = {Computer Networks},
  year = {2009},
  volume = {53},
  pages = {2321-2339}
}

@article{ozalp2,
  title = {Self-* properties through gossiping},
  author = {Ozalp Babaoglu and Mark Jelasity},
  journal = {Philosophical Transactions of the Royal Society A},
  year = {2008},
  volume = {366},
  pages = {3747-3757}
}

@inproceedings{berns,
author = {Andrew Berns and Sukumar Ghosh and Sriram Pemmaraju},
title = {A framework for building self-stabilizing overlay networks},
booktitle = {PODC},
note = {Brief Announcement},
 year ={2010},
 pages ={398-399}
 }

@inproceedings{jacob,
author = {Riko Jacob and Andrea Richa and Christian Scheideler and Stefan Schmid and Hanjo Taubig},
title = {A distributed polylogarithmic time
algorithm for self-stabilizing skip graphs},
booktitle = {PODC},
 year ={2009},
 pages ={131-140}
 }

@inproceedings{doerr,
author = {Benjamin Doerr and Tobias Friedrich and Thomas Sauerwald},
title = {Quasi-random rumor spreading},
booktitle = {SODA},
 year ={2008},
 pages ={773-781}
 }
 
 @inproceedings{flavio,
author = {Flavio Chierichetti and Silvio Lattanzi and
Alessandro Panconesi},
title = {Almost tight bounds on rumor spreading and conductance},
booktitle = {STOC},
 year ={2010},
 pages = {399-408}
 }
 
 @inproceedings{giakkoupis,
author = {Geroge Giakkoupis},
title = {Tight bounds
for rumor spreading in graphs of a
given conductance},
booktitle = {STACS},
 year ={2011},
 pages ={57-68}
 }
 

@book{b1,
  title = {Handbook of Graphs and Networks},  
  author = {Stefan Bornholdt and Heinz Georg Schuster (Editors)},
  publisher = {Wiley-VCH},
  year = {2003},
}

@book{b2,
  title = {Structure and Dynamics of Networks},  
  author = {Mark J. Newman and Albert-Laszlo Barabasi and Duncan J. Watts},
  publisher = {Princeton University Press},
  year = {2006}
}

@book{b3,
  title = {Complex Social Networks},  
  author = {Fernando Vega-Redondo},
  publisher = {Cambridge University Press},
  year = {2007}
}

@inproceedings{law-siu,
author = {Ching Law and Kai-Yeung Siu},
title = {An {$O(\log n)$} randomized resource discovery
algorithm},
booktitle = {DISC},
note = {Brief Announcement},
 year ={2000},
 pages ={5-8}
 }
 
 @INPROCEEDINGS{frieze1,
    author = {Soumen Chakrabarti and Alan Frieze and Juan Vera},
    title = {The Influence of Search Engines on Preferential Attachment},
    booktitle = {SODA},
    year = {2005},
    pages ={293-300}
}

 
@INPROCEEDINGS{frieze2,
    author = {Colin Cooper and Alan Frieze},
    title = {Crawling on Web Graphs},
    booktitle = {STOC},
    year = {2002},
    pages = {419-427}
}
 

@inproceedings{kuhn+lo:dynamic,
  title = {Distributed Computation in Dynamic Networks},
  author = {Fabian Kuhn and Nancy Lynch and Rotem Oshman},
  booktitle = {STOC},
  year = {2010},
  pages = {513-522}
}

@inproceedings{kempe1, 
author = {David Kempe and Jon Kleinberg},
title ={Protocols and Impossibility Results for Gossip-Based Communication
Mechanisms}, 
booktitle = {FOCS},
year = {2002},
pages ={471-480}
}

@inproceedings{kempe2, 
author = {David Kempe and Jon Kleinberg and Alan Demers},
title ={Spatial Gossip and Resource Location Protocols}, 
booktitle = {STOC}, 
year = {2001},
pages = {163-172}
}


@article{chernoff,
  title = {Asymptotic efficiency for tests based on the sum of observations},
  author = {H. Chernoff},
  journal = {Math. Stat.},
  year = {1952},
}

@article{hoeffding,
  title = {Probability for sums of bounded random variables},
  author = {W. Hoeffding},
  journal = {Journal of American Statistical Association},
  year = {1963}
}

@article{angluin,
  title = {Fast probabilistic algorithms for Hamiltonian circuits and matchings},
  author = {D. Angluin and L.G. Valiant},
  journal = {Journal of Computer and System Sciences},
  year = {1979}
}

@book{upfal,
  title = {Probability and Computing: Randomized Algorithms and Probabilistic Analysis},
  author = {Michael Mitzenmacher and Eli Upfal},
  publisher = {Cambridge University Press},
  year = {2005}
}

@article{jain+ms:steiner,
  title = {Packing Steiner trees},
  author = {K. Jain and M. Mahdian and M. Salavatipour},
  journal = {SODA},
  year = {2003},
}

@article{cheriyan+s:steiner,
  title = {Hardness and Approximation Results for Packing Steiner Trees},
  author = {J. Cheriyan and M. Salavatipour},
  journal = {Algorithmica},
  year = {2006},
}

@article{charikar+ccdgg:steiner,
  title = {Approximation Algorithms for Directed Steiner Problems},
  author = {M. Charikar and C. Chekuri and T. Cheung and Z. Dai and A. Goel and S. Guha},
  journal = {Journal of Algorithms},
  year = {1998},
}

@article{lau:steiner,
  title = {An approximate max-steiner-tree-packing min-steiner-cut theorem},
  author = {L.C. Lau},
  journal = {FOCS},
  year = {2004},
}

@article{guruswami+krsy,
  title = {Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems},
  author = {V. Guruswami and S. Khanna and R. Rajaraman and B. Shepherd and M. Yannakakis},
  journal = {STOC},
  year = {1999},
}

@article{ittai,
 author = {Ittai Abraham and Danny Dolev},
 title = {Asynchronous resource discovery},
 journal = {Computer Networks},
 volume = {50},
 issue = {10},
 month = {July},
 year = {2006},
 issn = {1389-1286},
 pages = {1616--1629},
 numpages = {14}
}

@INPROCEEDINGS{leighton,
    author = {Mor Harchol-Balter and Frank Thomson Leighton and Danny Lewin},
    title = {Resource Discovery in Distributed Networks},
    booktitle = {PODC},
    year = {1999},
    pages = {229--237}
}

@inproceedings{kutten,
  title = {Deterministic Resource Discovery in Distributed Networks},
  author = {Shay Kutten and David Peleg and Uzi Vishkin},
  booktitle = {SPAA},
  year = {2001},
  pages = {77-83}
}

@inproceedings{dimitriov+p:coupon,
  author    = {Nedialko B. Dimitrov and
               C. Greg Plaxton},
  title     = {Optimal Cover Time for a Graph-Based Coupon Collector Process},
  booktitle = {ICALP},
  year      = {2005},
  pages     = {702-716}
}

@inproceedings{adler+hkv:p2p,
  author    = {Micah Adler and
               Eran Halperin and
               Richard M. Karp and
               Vijay V. Vazirani},
  title     = {A stochastic process on the hypercube with applications
               to peer-to-peer networks},
  booktitle = {STOC},
  year      = {2003},
  pages     = {575-584},
}

@article{alon:combinatorics,
    author = {Noga Alon},
    title = {Problems and results in extremal combinatorics -- {II}},
    journal = {Discrete Mathematics},
    year = {2008},
    volume = {308},
    number = {19},
    pages = {4460-4472}   
}

@inproceedings{chen-spaa1,
  author    = {J. Chen and G. Pandurangan},
  title     = {Optimal Gossip-based Aggregate Computation},
  booktitle = {SPAA},
  year      = {2010},
  pages     = {124-133}
}

@inproceedings{demers,
 author = {Alan Demers and Dan Greene and Carl Hauser and Wes Irish and John Larson and Scott Shenker and Howard Sturgis and Dan Swinehart and Doug Terry},
 title = {Epidemic algorithms for replicated database maintenance},
 booktitle = {PODC},
 year = {1987},
 pages = {1--12},
 }

@inproceedings{shah,
 author = {Damon Mosk-Aoyama and Devavrat Shah},
 title = {Computing separable functions via gossip},
 booktitle = {PODC},
 year = {2006},
 pages = {113--122}
 }

@inproceedings{karp,
 author = {Richard M. Karp and Christian Schindelhauer and Scott Shenker and Berthold V\"{o}cking},
 title = {Randomized rumor spreading},
 booktitle = {FOCS},
 year = {2000},
 isbn = {0-7695-0850-2},
 pages = {565--574},
 publisher = {},
 address = {},
 }

@article{DRG,
  author =       {J. Chen and G. Pandurangan and D. Xu},
  title =        {Robust aggregate computation in wireless sensor network: distributed randomized algorithms and analysis},
  journal =    {IEEE Trans. on Parallel and Distributed Systems},
  volume        = {17},
  number        = {9},
  year =         {Sep. 2006},
  pages  =       {987--1000},
}

@conference{kempe,
author ={D. Kempe and A. Dobra and J. Gehrke},
title={Gossip-based Computation of
Aggregate Information},
booktitle={FOCS},
year={2003},
pages={482--491},
}

@article{boyd,
 author = {Stephen Boyd and Arpita Ghosh and Balaji Prabhakar and Devavrat Shah},
 title = {Randomized gossip algorithms},
 journal = {IEEE Trans. on Infor. Theory},
 volume = {52},
 number = {6},
 year = {2006},
 pages = {2508--2530}
  }
  
@inproceedings{doerr+ff:rumor,
author = {Benjamin Doerr and Mahmoud Fouz and Tobias Friedrich},
title = {Social networks spread rumors in sublogarithmic time},
booktitle = {STOC},
 year ={2011},
 pages ={21-30}
 }
 
@inproceedings{clementi+cdfipps:evolving,
	Author = {Andrea E. F. Clementi and Pierluigi Crescenzi and Carola Doerr and Pierre Fraigniaud and Marco Isopi and Alessandro Panconesi and Francesco Pasquale and Riccardo Silvestri},
	Booktitle = {ESA},
	Pages = {325--336},
	Title = {Rumor Spreading in Random Evolving Graphs},
	Year = {2013}
}

